1. Field of the Invention
The present invention relates to an encrypting method, a deciphering method and a certifying method, and more particularly to an encrypting method, a deciphering method and a certifying method adapted for use in various information services.
2. Related Background Art
Ciphers can be generally classified into (A) common ciphers and (B) public key ciphers.
The common cipher (A) employs one and the same key secretly owned by the transmitter and the receiver, and is also called a common key cipher or a secret key cipher.
In the public key cipher (B), the enciphering key and the deciphering key are mutually different, and the encrypting key is made publicly open while the deciphering key is held secret. In the following there will be given an explanation of the public key cipher, with respect to (a) features, (b) protocol, (c) a representative example, and (d) the RSA cipher as a specific example thereof.
(a) Features of the Public Key Cipher
1. Since the encrypting key and the deciphering key are different and the encrypting key can be made public, it is not necessary to deliver the encrypting key in secret, and thus the key delivery is made easier.
2. Since the encrypting key of each user is made public, each user is only required to maintain the deciphering key secret.
3. There can be realized a certifying function allowing the receiver to confirm that the transmitter of the transmitted message is not false and that the transmitted message has not been tampered with.
(b) Protocol of the Public Key Cipher
For a message M to be communicated, with a public encrypting key kP (hereinafter called public key) for defining an encrypting operation E(kP, M) and a secret deciphering key kS for defining a deciphering operation D(kS, M), the public key cipher algorithm in the first place satisfies the following two conditions:
(1) If the public key kP is known, the encrypting operation E(kP, M) can be easily calculated. Also if the secret key kS is known, the deciphering operation D(kS, M) can be easily calculated.
(2) In a case where the secret key kS is not known, even if the above-mentioned public key kP and the calculating procedure C=E(kP, M) for the above-mentioned enciphering operation E are known, the determination of the message M is difficult in consideration of the amount of calculation.
The secret communication can be realized by satisfying the following condition (3), in addition to the foregoing conditions (1) and (2):
(3) The encrypting operation E(kP, M) can be defined for all the messages (plain texts) M, and there stands a relation:
D(kS, E(kP, M))=M
Thus, since the kP is made public, anybody can execute the calculation of the encrypting operation E(kP, M), but the restoration of the message M through the deciphering operation D(kS, E(kP, M)) can only be made by the person who has the secret key kS. On the other hand, the certified communication can be realized by satisfying the following condition (4), in addition to the foregoing conditions (1) and (2):
(4) D(kS, M) can be defined for all the messages (plain texts) M, and there stands a relation:
E(kP, D(kS, M))=M
The deciphering operation D(kS, M) can be calculated only by the proper holder of the secret key kS, and, even if another person pretends to be such proper holder of the secret key kS by calculating D(kSxe2x80x2, M) with a false secret key kSxe2x80x2, the receiver can confirm that the received information is false since E(kP, D(kSxe2x80x2, M))xe2x89xa0M. Also if D(kS, M) is tampered with, there results E(kP, D(kS, M)xe2x80x2)xe2x89xa0M, so that the receiver can confirm that the received information is improper.
In the following there will be shown the protocols of secret communication, certified communication and secret communication with signature from a transmitter A to a receiver B by the public key cipher, wherein the transmitter A is assumed to have a secret key kSA and a public key kPA, and the receiver B is assumed to have a secret key kSB and a public key kPB.
Secret Communication
The secret communication of a message (plain text) M from the transmitter A to the receiver B is executed in the following procedure.
At first, in a step 1, the transmitter A encrypts the message M with the public key kPB of the receiver B and sends the cipher text C to the receiver B, wherein:
C=E(kPB, M).
Then, in a step 2, the receiver B deciphers the received cipher text C with his own secret key kSB to obtain the original plain text M by:
M=D(kSP, C).
Since the public key kPB of the receiver B is made public to unspecified plural persons, the secret communication to the receiver B can be made not only by the transmitter A but also by any other person.
Certified Communication
The certified communication of a message (plain text) M from the transmitter A to the receiver B is executed in the following procedure.
At first, in a step 1, the transmitter A generates a transmission text S with his secret key kSA of the receiver A and sends it to the receiver B, wherein:
S=D(kSA, M).
The transmission text S mentioned above is called a signature text, and the operation of obtaining such signature text S is called signing.
Then, in a step 2, the receiver B executes the restoring conversion of the signature text S with the public key kPA of the transmitter A, thereby obtaining the original plain text M by:
M=E(kPA, S)
By the confirmation that the restored plain text M mentioned above constitutes a meaningful message, it is certified that the above-mentioned plain text M has certainly been transmitted from the transmitter A.
Since the public key of the transmitter A is made public to the unspecified plural persons, the signature text of the transmitter A can be certified not only by the receiver B but also any other person. Such certification is called digital signature.
Signed Secret Communication
The signed secret communication of a message (plain text) M from the transmitter A to the receiver B is executed in the following procedure.
At first, in a step 1, the transmitter A prepares a signed text S by signing the message M with the secret key kSA of the transmitter A, wherein:
xe2x80x83S=D(kSA, M).
Then the transmitter A encrypts the signed text S with the public key kPB of the receiver B and sends the cipher text C to the receiver B, where:
C=E(kPB, S).
Then, in a step 2, the receiver B deciphers the cipher text C with the secret key kSB of the receiver B to obtain the signed text S by:
S=D(kSB, C).
Also the receiver B executes the restoring conversion of the signed text S with the public key kPA of the transmitter A, thereby obtaining the original plain text M by:
M=E(kPA, S).
By the confirmation that the restored plain text M mentioned above constitutes a meaningful message, it is certified that the above-mentioned plain text M has certainly been transmitted from the transmitter A.
The order of applications of the functions in the foregoing steps of the signed secret communication may also be inverted. More specifically, in addition to the above-mentioned procedure:
C=E(kPB, D(kSA, M))xe2x80x83xe2x80x83Step 1
M=E(kP, D(kSB, C))xe2x80x83xe2x80x83Step 2
the signed secret communication can also be realized by the following procedure:
C=D(kSA, E(kPB, M))xe2x80x83xe2x80x83Step 1
xe2x80x83M=D(kSB, E(kPA, C))xe2x80x83xe2x80x83Step 2
(c) Specific Example of Public Key Cipher
As it is difficult to explain the individual cipher systems, in the following there will be explained the RSA cipher system as a specific example. The RSA cipher was invented by Rivest, Shamir and Adleman of MIT and was named after them.
The RSA cipher is presently one of the most promising public key ciphers. In the following, there will be explained the basic principle of the RSA cipher, in the order (1) key generation, (2) encrypting and (3) deciphering.
(1) Key Generation
The public key and the secret key are determined by the following algorithm.
1. Mutually different large prime numbers p, q are arbitrarily selected and the product n thereof is calculated by:
n=pq
2. The least common multiple L of (pxe2x88x921) and (qxe2x88x921) is calculated, and there is selected an arbitrary integer e, which is relatively prime to thus calculated least common multiple L and is smaller than the least common multiple by:
L=LCM((pxe2x88x921), (qxe2x88x921))
GCD(e, L)=1
1 less than e less than L
where LCM indicates the least common multiple and GCD indicates the greatest common divisor.
3. The following congruence equation is solved, based on the arbitrary integer e and the least common multiple L determined in the foregoing step 2:
edxe2x89xa11(mod L)
The values (e, n) thus determined are used as the encrypting key while those (d, n) are used as the deciphering key, in which e and n are the public keys while d is the secret key.
(2) Encrypting
For a plain text M and a cipher text C, the encrypting algorithm E is represented by:
C=E(M)=Memodn
where each of the plain text M and the cipher text C is an integer between 0 and nxe2x88x921. If the original message is larger than the integer n, it is divided into blocks of a size n and the encrypting or the deciphering process is applied in succession to such blocks.
(3) Deciphering
The deciphering algorithm D is represented by:
M=D(C)=Cdmodn
In the case of deciphering the plain text M encrypted by the above-mentioned encrypting algorithm E(M)=Memodn:
D(C)=D(E(M))xe2x89xa1(Me)dxe2x89xa1Medxe2x89xa1M(modn)
so that the original plain text M can be obtained.
Based on the above-explained principle, the public key can be disclosed for example in a telephone directory, and it is no longer necessary to maintain a key individually with each of the unspecified plural persons. Therefore, in contrast to the secret key cipher system, in which a key has to be secretly shared by the partners of communication prior to the execution of the communication, the public key cipher system has an advantage that the management and use of the keys are easier.
However, most public key cipher systems are unable, because of the structural limitations thereof, to select arbitrary public keys, so that the public key has merely been a number which is meaningless to the persons concerned.
On the other hand, a serious problem will arise unless the proper correlation is maintained between the key and the corresponding entity (entity of communication which is the user or the computer).
More specifically there will result a situation where a document intended for a person A is erroneously delivered to a person B, or a situation of xe2x80x9cpretensexe2x80x9d where a signature intended to be obtained from a person A is obtained from another person B.
However, as long as the public key is a number meaningless to the involved persons, the correlation between an entity and its public key cannot be verified directly by other arbitrary entities, so that the keys have to be managed by a key list to be publicized by a reliable organization.
On the other hand, a cipher system and signature method based on ID, capable of employing an ID (personalized identification information such as name or address) as the public key, have been proposed for example by, A. Shamir, xe2x80x9cIdentity-Based Cryptosystems and Signature Schemesxe2x80x9d, Proc. of Crypt. ""84, 1984 and by T. Okamoto and A. Shiraishi, xe2x80x9cSafe User Verifying Method by Single Management Informationxe2x80x9d, IN83-92, 1984.
Such systems, having a structure allowing the use of the ID of the entity as the public key, allows the user to understand the public key as the ID information. Since the correctness of the public key can be understood in an easier manner in comparison with other public key cipher systems, signature schemes, secret key cipher systems or identification systems, the list of keys can be dispensed with.
As an example of the ID-based cipher systems mentioned above, there will be explained, in the following, the system proposed by S. Tsujii, T. Ito and K. Kurosawa, xe2x80x9cID-Based Cryptosystems Using Discrete Logarithm Problemxe2x80x9d Elect. Lett., Vol. 23, No. 24, 1988.
Preparation
At first, in a step 1, the center publicizes n-dimensional vectors:
a=(a1, a2, . . . , an)
h=(h1, h2, . . . , hn)
h1=galmodp (1 less than 1 less than n)
based on a prime number p, an original element g of a Galois field GF(p) and a Galois field GF(p), and a one-dimensional function f.
Then, in a step 2, an entity i registers its ID:
IDi=(xi1, xi2, . . . , xik)
(k less than n), xi1xcex5{0, 1} (ixe2x89xa61xe2x89xa6k)
at the center.
Then, in a step 3, the center determines a modified ID:
EIDixcex94f(IDi)=(yi1, yi2, . . . yin)xe2x80x83xe2x80x83(1)
yi1xcex5{0, 1} (ixe2x89xa61xe2x89xa6n)
and calculates a secret key Si of the entity i:                               S          i                ≡                  xe2x80x83                ⁢                              ∑                          1              ≤              j              ≤              n                                ⁢                                    a              j                        ⁢                          y              ij                        ⁢                          xe2x80x83                        ⁢            mod            ⁢                          xe2x80x83                        ⁢            p                                                  ≡                  xe2x80x83                ⁢                                            EID              i                        ·            a                    ⁢                      xe2x80x83                    ⁢          mod          ⁢                      xe2x80x83                    ⁢          p                    
and sends it to the entity i through a safe communication path.
Encrypting
The transmitting entity j at first determines an arbitrary integer k, which is a secret of the transmitter only. Then it enters the ID of the receiving entity i into the encrypting apparatus, which generates EIDi according to the foregoing function (1) and calculates the product Zi of the elements h1, for which the corresponding yi1 is 1, among the elements h, namely:       Z    i    ⁢      =    Δ    ⁢            ∏              l        =        1            N        ⁢          xe2x80x83        ⁢                  h        l                  y          il                    ⁢              xe2x80x83            ⁢      mod      ⁢              xe2x80x83            ⁢      p      
zi can in fact be represented by:       Z    i    ≡            ∑                        g          l                =        1            N        ⁢                  a        l            ⁢              y        il              ≡            g              S        i              ⁢          xe2x80x83        ⁢    mod    ⁢          xe2x80x83        ⁢    p  
The transmitting entity j prepares a cipher text:
Cxe2x89xa1(gk, MZik)mod p
from a plain text M according to the El Gamal cipher system, and sends the cipher text to the receiving entity i.
Deciphering
The receiving entity i calculates the Si-th power of the first term gk of the received cipher text C to obtain:
(gk)Sixe2x89xa1(gSi)kxe2x89xa1Zikmod p
and divides the second term with Zik to obtain the plain text M.
In the following, as an example of the xe2x80x9cID-Based Signature Schemexe2x80x9d, there will be explained a system proposed by A. Fiat and A. Shamir, xe2x80x9cHow to Prove Yourself: Practical Solution to Identification and Signature Problemsxe2x80x9d, Proc. Of Crypt. ""86, 1986.
System Preparation
The center selects prime numbers p and q, and publicizes the product N thereof and a one-directional function f for converting an arbitrary character train into [0, N).
An entity A receives a secrecy sAj for its identifier IA from the center. The center confirms the correctness of IA of the entity, then determines:
IDAj=f(IA, j)
where j is a small parameter, then calculates:
sAj=1/I DAjmod N
and transfers it to the entity A (for the purpose of simplicity, representation is made as j=1, 2, 3, . . . k).
Generation of Signature
The entity A signs the plain text M.
In a step 1, the entity A generates random numbers:
xcex31, . . . xcex3txcex5[0, N)
and calculates:
xi=yi2 mod N
Then, in a step 2, the entity A calculates:
f(M, x1, . . . , xt)
and takes the initial kt bits as the value of eij, where:
xe2x80x83(1xe2x89xa6ixe2x89xa6t, 1xe2x89xa6jxe2x89xa6k)
In a next step 3, the entity A calculates:       y    i    =            r      i        ⁢                  ∏                              e            ij                    =          1                    ⁢              xe2x80x83            ⁢                        s          Aj                ⁢                  xe2x80x83                ⁢        mod        ⁢                  xe2x80x83                ⁢        N        ⁢                  xe2x80x83                ⁢                  (                                    i              =              1                        ,            …            ⁢                          xe2x80x83                        ,            t                    )                    
and takes IA, M, eij and yi as the digital signature.
Verification of Signature
An entity B, receiving IA, M, eij and yi, calculates:
IDAj=f(IA, j) (1xe2x89xa6jxe2x89xa6k),
      z    i    =            y      i      2        ⁢                  ∏                              e            ij                    =          1                    ⁢              xe2x80x83            ⁢                        ID          Aj                ⁢                  xe2x80x83                ⁢        mod        ⁢                  xe2x80x83                ⁢        N        ⁢                  xe2x80x83                ⁢                  (                      1            ≤            i            ≤            t                    )                    
and confirms that the initial kt bits of f(M, z1, . . . , zi) coincide with eij.
In the following, there will be explained, as an example of the ID-based shared key (key delivery) system, a system proposed by E. Okamoto, xe2x80x9cID-Based Key Delivery Systemxe2x80x9d, ISEC88-6, 1988.
Preparation
The center generates a modulus n, a public key e and a secret key d. The center is assumed to be reliable and d is maintained as the secret of the center.
Entry of User
The center transfers (IDx, sx, n, e, g) to a user X, wherein g is a constant, and sx is represented by:
sx=IDxxe2x88x92d mod n
Generation of Work Key
In the following it is assumed that a key is generated between entities A and B. In a step 1, the entity A generates a random number rA and sends:
xA=SAxe2x80xa2grA mod n
to the entity B, which similarly generates a random number rB and provides the entity A with:
x=SBxe2x80xa2gBE mod n
In a step 2, the entity A obtains:
WKAB=(IDBxe2x80xa2xeB)rA=gexe2x80xa2rAxe2x80xa2rB mod n
while the entity B obtains:
WKAB=(IDAxe2x80xa2xeA)rB=gexe2x80xa2rAxe2x80xa2rB mod n
In the following, as an example of the ID-based identification confirmation system, there will be explained the foregoing system proposed by A. Fiat and A. Shamir, xe2x80x9cHow to Prove Yourself: Practical Solution to Identification and Signature Problemsxe2x80x9d, Proc. Of Crypt. ""86, 1986.
System Preparation
This is the same as that described in connection with ID-based signature scheme.
Confirmation of Identity
An entity A proves that it is truly A, to another entity B.
In a step 1, the entity A sends IA to the other entity B.
Then, in a step 2, the other entity B calculates f(IA, j) (j=1, 2, . . . , k).
Then, following steps 3 to 6 are repeated from i=1 to i=t.
In the step 3, the entity A generates a random number r1 xcex5[0, n) and sends xi=ri2 mod n to the other entity B.
In the step 4, the other entity B sends a random binary vector (ei1, . . . , eik) to the entity A.
In the step 5, the entity A sends, to the other entity B:       y    i    =            r      i        ⁢                  ∏                              e            ij                    =          1                    ⁢              xe2x80x83            ⁢                        s          Aj                ⁢                  xe2x80x83                ⁢        mod        ⁢                  xe2x80x83                ⁢        N        ⁢                  xe2x80x83                ⁢                  (                                    i              =              1                        ,            …            ⁢                          xe2x80x83                        ,            t                    )                    
In the step 6, the other entity B confirms:       x    i    ⁢      =    ?    ⁢            y      i      2        ⁢                  ∏                              e            ij                    =          1                    ⁢              xe2x80x83            ⁢                        ID          Aj                ⁢                  xe2x80x83                ⁢        mod        ⁢                  xe2x80x83                ⁢        N            
However, pretense may not be completely preventable even if the ID is taken as the public key. For example, in a case of effect communication by exchanging the ID with a business partner, there can be considered a case where the given ID is not of such business partner itself but of another similar person or of an entirely different person.
Stated differently, even in the ID-based cipher systems and signature schemes, though the public key has an understandable meaning, the adequacy of the given ID cannot be securely identified from the ID alone. Consequently the proper correspondence between the entity providing the public key (ID) and the provided public key (ID) is still not guaranteed, as in other public key systems.
An object of the present invention is to resolve the above-mentioned drawbacks.
Another object of the present invention is to provide an encrypting method, a deciphering method and a certifying method allowing secure confirmation of the correspondence between the entity itself and its public key, thereby preventing so-called pretense.
The foregoing objects can be attained, according to the present invention, by an encrypting method which is featured by the encrypting employing information correlated with an attribute of the entity as a key. In a preferred embodiment, the above-mentioned attribute is the biophysical attribute information of the entity.
Also according to the present invention, there is provided a certifying method which is featured by judging the adequacy of the correspondence between the key and the entity, based on the result of comparison of the attribute information of the entity and the information provided as the key of the entity.
Still other objects of the present invention, and the features thereof, will become fully apparent from the following detailed description of the embodiments, to be taken in conjunction with the attached drawings.